Coloring is used in wireless networks to improve communication efficiency,mainly in terms of bandwidth, energy and possibly end-to-end delays. In thispaper, we define the h-hop node coloring problem, with h any positive integer,adapted to two types of applications in wireless networks. We specify bothgeneral mode for general applications and strategic mode for data gatheringapplications.We prove that the associated decision problem is NP-complete. Wethen focus on grid topologies that constitute regular topologies for large ordense wireless networks. We consider various transmission ranges and identify acolor pattern that can be reproduced to color the whole grid with the optimalnumber of colors. We obtain an optimal periodic coloring of the grid for theconsidered transmission range. We then present a 3-hop distributed coloringalgorithm, called SERENA. Through simulation results, we highlight the impactof node priority assignment on the number of colors obtained for any networkand grids in particular. We then compare these optimal results on grids withthose obtained by SERENA and identify directions to improve SERENA.
展开▼
